#include <vector>
#include <iostream>
#include <random>
#include <algorithm>
#include <ctime>

/**
 * C++标准库
 * 二分搜索操作（在已排序范围上）
 * 定义于头文件 <algorithm>
 * lower_bound                  返回指向第一个不小于给定值的元素的迭代器(函数模板)
 * ranges::lower_bound(C++20)   返回指向首个不小于给定值的元素的迭代器(niebloid)
 * upper_bound                  返回指向第一个大于给定值的元素的迭代器(函数模板)
 * ranges::upper_bound(C++20)   返回指向首个大于某值的元素的迭代器(niebloid)
 * binary_search                确定元素是否存在于某范围中(函数模板)
 * ranges::binary_search(C++20) 确定元素是否存在于某范围中(niebloid)
 * equal_range                  返回匹配特定键值的元素范围(函数模板)
 * ranges::equal_ranges(C++20)  返回匹配特定值的元素范围(niebloid)
 **/
using namespace std;

int binary_search(vector<int>& vec, int item)
{
    int low = 0, high = vec.size() - 1, mid, guess;
    while (low <= high) {
        mid = (low + high) / 2;
        guess = vec[mid];
        if(guess == item) return mid;
        else if (guess > item) high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}

int main()
{
    default_random_engine e(time(NULL));
    vector<int> vec;
    int len = 30;
    for (int i = 0; i < len; i++){
        vec.push_back(e() % 100);
    }
    sort(vec.begin(), vec.end());
    for (auto &i : vec){
        cout << i << " ";
    }
    int item = e() % 100;
    cout << endl << item << endl;
    int position = binary_search(vec, item);
    cout << position << endl;
    return 0;
}